#!/usr/bin/env python
#==============================================================================
#
#  $Id$
#
"""
    Unit tests of the second-generation btree code.
"""
#
#   Copyright (C) 2007 Michael A. Muller
#
#   This file is part of ODB.
#
#   ODB is free software: you can redistribute it and/or modify it under the 
#   terms of the GNU Lesser General Public License as published by the Free 
#   Software Foundation, either version 3 of the License, or (at your option) 
#   any later version.
#
#   ODB is distributed in the hope that it will be useful,
#   but WITHOUT ANY WARRANTY; without even the implied warranty of
#   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#   GNU Lesser General Public License for more details.
#
#   You should have received a copy of the GNU Lesser General Public License 
#   along with ODB.  If not, see <http://www.gnu.org/licenses/>.
#
#==============================================================================

import unittest, string
import fixpath
from utils import SortedList
from odb.btree import BTreeMeat, BTreeRoot, BListKeyMaster, FindData, \
    BTreeElem, BListFindData, BList, BTree

class test_btree(unittest.TestCase):

    def testInsert(self):
        node = BTreeRoot([], BListKeyMaster(0), None)
        findData = FindData()
        findData.push(node)
        valNode = BTreeElem(100, BListKeyMaster(), None)
        node.insert(findData, valNode)
        
        findData = BListFindData(0)
        node.find(findData)
        self.assertEquals(findData.getParent().node, node)
        self.assertEquals(findData.node, valNode)

class TestBListSequences(unittest.TestCase):

    def setUp(self):
        self.blist = BList()
        self.list = []
    
    def insert(self, index, val):
        self.blist.insert(index, val)
        self.list.insert(index, val)
    
    def append(self, val):
        self.blist.append(val)
        self.list.append(val)
    
    def remove(self, index):
        del self.blist[index]
        del self.list[index]

    def check(self):
        """
            Check the b-tree list against the reference list.
        """
        for i in xrange(len(self.list)):
            self.assertEquals(self.list[i], self.blist[i])
        self.assertRaises(IndexError, self.blist.__getitem__, len(self.list))

    def cursorCheck(self):
        """
            Just like @check() only use a cursor.
        """
        cur = self.blist.cursor()
        for e in self.list:
            self.assertEquals(e, cur.next())
        self.assertRaises(StopIteration, cur.next)

    def testOverflows(self):
        seq = [0, 1, 2, 3, 4, 5, 6, 7]
        blist = BList()
        for x in seq:
            self.append(x)
#        self.blist.dump()
        self.check()
        
    def testBListInsert(self):
        seq = [(0, 1), (0, 0), (1, 0.5), (1, 0.2)]
        for index, val in seq:
            self.insert(index, val)
            self.check()
    
    def testBListDelete(self):
        self.insert(0, 1)
        self.remove(0)
        self.check()

        for x in range(9):
            self.append(x)

        # this is a carefully crafted attack on edge conditions...
        self.remove(1)          # last slot of first node
        self.remove(3)          # first slot of second node
        self.remove(6)          # last slot of last node
        self.check()
    
    def testIteration(self):
        for x in [0, 1, 2, 3, 4, 5, 6]:
            self.append(x)
        self.cursorCheck()
    
    def testFound(self):
        cur = self.blist.cursor()
        self.assertFalse(cur.setToFirst().found())
        self.append(100)
        self.assert_(cur.setToFirst().found())
        self.assertFalse(cur.setToLast().found())
        self.assert_(cur.setToKey(0).found())
        self.assertFalse(cur.setToKey(1).found())
    
    def testCursorInserts(self):
        cur = self.blist.cursor()
        cur.setToFirst()
        cur.insert(100)
        self.list.append(100)
        cur.setToLast()
        cur.insert(200)
        self.list.append(200)
        cur.setToKey(1)
        cur.insert(150)
        self.list.insert(1, 150)
        self.check()

    def testLen(self):
        for i in range(7):
            self.blist.append(i)
        self.assertEquals(len(self.blist), i + 1)

class TestBTrees(unittest.TestCase):

    def setUp(self):
        self.btree = BTree()
        self.slist = SortedList()
    
    def check(self):
        for key, val in self.slist:
            self.assertEquals(val, self.btree[key])
        
        # make sure that the last key is the last key in the btree
        if self.slist:
            cur = self.btree.cursor()
            cur.setToKey(key)
            cur.next()
            self.assertRaises(StopIteration, cur.next)
    
    def set(self, key, val):
        self.btree[key] = val
        self.slist.add(key, val)
    
    def delete(self, key):
        del self.btree[key]
        self.slist.remove(key)

    def createSampleData(self):
        self.set('test', 100)
        self.set('other', 200)
        self.set('value', 300)
        self.set('bogus', 800)
    
    def testInsert(self):
        self.createSampleData()
        self.check()
    
    def testDelete(self):
        self.createSampleData()
        self.delete('test')
        self.delete('value')
        self.delete('bogus')
        self.delete('other')
        self.check()
    
    def testFound(self):
        cur = self.btree.cursor()
        self.assertFalse(cur.setToFirst().found())
        self.set('first', 100)
        self.assert_(cur.setToFirst().found())
        self.assertFalse(cur.setToLast().found())
        self.assert_(cur.setToKey('first').found())
        
        # test non-existent keys before and after the existing key
        self.assertFalse(cur.setToKey('nonexistent').found())
        self.assertFalse(cur.setToKey('alsoNonexistent').found())

    def testCursorInserts(self):
        cur = self.btree.cursor()
        cur.setToKey('first')
        cur.insert(100)
        self.slist.add('first', 100)
        cur.setToKey('last')
        cur.insert(200)
        self.slist.add('last', 200)
        cur.setToKey('inner')
        cur.insert(150)
        self.slist.add('inner', 150)
        self.check()
    
    def testReplace(self):
        cur = self.btree.cursor()
        cur.setToKey('first')
        cur.insert(100)
        cur.setToKey('first')
        cur.setValue(200)
        self.slist.add('first', 200)
        self.check()

    def testCursorOnEmpty(self):
        for key, val in self.btree.cursor():
            self.fail('cursored an element on an empty btree')
    
    def testGetKeyOnEmpty(self):
        # XXX blatant evidence of a broken invariant - getKey() should always 
        # return None when there is no matching node
        cur = self.btree.cursor()
        cur.setToFirst()
        self.assertEquals(cur.getKey(), '')
        
        cur.setToKey('nonexistent')
        self.assertEquals(cur.getKey(), None)
    
unittest.main()